import collections
from typing import List


class Solution:
    def movesToChessboard(self, board: List[List[int]]) -> int:
        n = len(board)
        rows = collections.Counter()
        cols = collections.Counter()
        for i in range(n):
            rows[tuple(board[i])] += 1
            cols[tuple(board[j][i] for j in range(n))] += 1
        # print(rows, cols)

        if len(rows) != 2 or len(cols) != 2:
            return -1

        ans = 0

        infos = [[rows.popitem(), rows.popitem()], [cols.popitem(), cols.popitem()]]
        for t in range(2):
            info = infos[t]

            n1, v1 = info[0]
            n2, v2 = info[1]

            for i in range(n):
                if n1[i] == n2[i]:
                    return -1

            if n % 2 == 0:
                if v1 != v2:
                    return -1

                m1, m2 = 0, 0
                for i in range(n):
                    if (t == 0 and board[i][0] == n1[0]) or (t == 1 and board[0][i] == n1[0]):
                        if i % 2 == 0:
                            m1 += 1
                        else:
                            m2 += 1

                ans += min(m1, m2)

            else:
                if v1 > v2:
                    n1, v1, n2, v2 = n2, v2, n1, v1

                # print(n1, v1, n2, v2)

                if v2 - v1 != 1:
                    return -1

                res = 0
                for i in range(n):
                    if i % 2 == 0:
                        if (t == 0 and board[i][0] != n2[0]) or (t == 1 and board[0][i] != n2[0]):
                            res += 1

                ans += res

        return ans


if __name__ == "__main__":
    # 2
    print(Solution().movesToChessboard(board=[[0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1]]))

    # 0
    print(Solution().movesToChessboard(board=[[0, 1], [1, 0]]))

    # -1
    print(Solution().movesToChessboard(board=[[1, 0], [1, 0]]))

    # 测试用例45/124
    print(Solution().movesToChessboard([[1, 0, 0], [0, 1, 1], [1, 0, 0]]))  # 1

    # 测试用例105/124
    print(Solution().movesToChessboard([[0, 1, 0], [1, 0, 1], [0, 1, 0]]))  # 0

    # 测试用例94/124
    print(Solution().movesToChessboard([[1, 1, 1, 1], [1, 1, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0]]))  # -1
